I. Technical Field
The present invention pertains generally to telecommunications, and particularly to the compression of headers of packets such as media packets. The technical field is illustrated by the following (all of which are incorporated herein by reference): (1) U.S. patent application Ser. No. 10/987,218, filed Nov. 15, 2004, entitled “Method and Apparatus for Handling Out-Of-Sequence Packets in Header Compression”; (2) U.S. patent application Ser. No. 10/673,345. filed Sep. 30, 2003, entitled “Header Compression Method”; (3) U.S. patent application Ser. No. 10/987,219, filed Nov. 15, 2004, entitled “Method and Apparatus for Header Compression With Transmission of Context Information Dependent Upon Media Characteristic”; (4) PCT application PCT/SE2005/000158 filed on Feb. 8, 2005: (5) U.S. Provisional Application Ser. No. 60/744,716, filed Apr. 12, 2006, entitled “Method for Combining Ciphering and Compression”; (6) U.S. Provisional Application Ser. No. 60/744,719, filed Apr. 12, 2006. entitled “Methods for Shared Sequence Numbering and Checksums Between Multiple Co-Located Functions”; (7) U.S. Provisional Application Ser. No. 60/744,721. filed Apr. 12, 2006, entitled “Methods for Combined Management of Cryptographic and Compression Contexts”; and (7) U.S. Provisional Application Ser. No. 60/744,724, filed Apr. 12, 2006, entitled “Methods for Secure Robust Header Compression”.
The technology herein described is very generally applicable to header compression, and is not confined to current mechanisms to the ROHC algorithm and encoding methods, but rather proposes new mechanisms to better tailor compression based on the actual characteristics of the underlying link in the presence of reordering.
II. Related Art and Other Considerations
Related art includes PCT Patent Publication WO 01/35534 A2, titled “Variable-length encoding of compressed data”. However, PCT Patent Publication WO 01/35534 A2 applies to coding of fields incrementing sequentially, in order to provide robustness against losses for those fields.
Other related documents include Kapoor, R., Haipeng J. and M. Kretz, Robust Header Compression (ROHC): Support for Reordering and Constant IP-ID, Internet Draft (work in progress), <draft-ietf-kapoor-rohc-rtp-new-requirements-00.txt>, March 2005, which is an IETF ROHC working group proposal for new requirements to ROHC. Kapoor provides suggestions on how to improve robustness to reordering for the LSB encoding of sequentially incrementing fields are proposed, but addresses the problem differently.
Due to the tremendous success of the Internet, it has become a challenging task to make use of the Internet Protocol (IP) over all kinds of links. However, because of the fact that the headers of the IP protocols are rather large, it is not always a simple task to make this come true for narrowband links, such as cellular links, for example. As an example, consider ordinary speech data transported by the protocols (IP, UDP, RTP) used for Voice-over-IP (VoIP), where the header may represent about 70% of the packet resulting in a very inefficient usage of the link.
The term “header compression” (HC) encompasses the art of minimizing the necessary bandwidth for information carried in headers on a per-hop basis over point-to-point links. Header compression techniques in general have a more than ten-year-old history within the Internet community. Several commonly used header compression protocols exist, such as the following: (1) Van Jacobson, Compressing TCP/IP Headers for Low-Speed Serial Links. IETF RFC 1144, IETF Network Working Group, February 1990; (2) Mikael Degermark, Björn Nordgren, Stephen Pink, IP Header Compression, IETF RFC 2507, IETF Network Working Group, February 1999; and (3) Steven Casner, Van Jacobson. Compressing IP/UDP/RTP Headers for Low-Speed Serial Links, IETF RFC 2508, IETF Network Working Group. February 1999, all of which are incorporated by reference herein in their entirety.
Header compression takes advantage of the fact that some fields in the headers are not changing within a flow, or change with small and/or predictable values. Header compression schemes make use of these characteristics and send static information only initially, while changing fields are sent with their absolute values or as differences from packet to packet. Completely random information has to be sent without any compression at all.
Header compression is thus an important component to make IP services over wireless, such as voice and video services, economically feasible. Header compression solutions have been developed by the Robust Header Compression (ROHC) Working Group of the Internet Engineering Task Force (IETF) to improve the efficiency of such services.
Robust Header Compression (ROHC), as defined in RFC 3095 (“[ROHC]”, i.e., Bormann, C., “RObust Header Compression (ROHC): Framework and four profiles: RTP, UDP, ESP, and uncompressed”, RFC 3095. Internet Engineering Task Force, July 2001), is an extensible framework for which profiles for compression of various protocols may be defined. For real-time multimedia services (e.g. voice, video), the application data is transported end-to-end within an IP/UDP/RTP stream. Header compression of IP/UDP/RTP is defined by the ROHC profile 0x0001 (ROHC RTP) and is applicable for Voice-over-IP (VoIP) services among others. The ROHC RTP header compression scheme has been designed to efficiently compress the P/UDP/RTP headers over an arbitrary link layer.
A number of other ROHC profiles have also been defined for compression. Among these are (1) IP/UDP/RTP headers (described in: Jonsson, L. and G. Pelletier. RObust Header Compression (ROCH): A Link-Layer Assisted ROHC Profile for IP/UDP/RTP, IETF RFC 3242, April 2002; and Liu, Z and K. Le, Zero-byte Support for Bidirectional Reliable Mode (R-mode) in Extended Link-Layer Assisted RObust Header Compression (ROHC) Profile, IETF RFC 3408, December 2002); (2) IP only headers (described in: Jonsson, L. and G. Pelletier, RObust Header Compression (ROHC): A compression profile for IP, IETF RFC 3843, June 2004); (3) IP/TCP headers (described in: Pelletier, G., Jonsson, L., et al., RObust Header Compression (ROHC): A Profile for TCP/IP (ROHC-TCP), Internet Draft (work in progress), <draft-ietf-rohc-tcp-11.txt>, Jan. 4, 2006); and (4) IP/UDP-Lite/RTP headers (described in: Pelletier, G., RObust Header Compression (ROHC): Profiles for UDP-Lite, IETF RFC 4019, March 2005). All RFCs cited herein are incorporated by reference herein in their entireties.
Except for negotiation (see also Bormann, C., Robust Header Compression (ROHC) over PPP, IETF RFC 3241, April 2002), ROHC profiles only requires framing and error detection to be provided by the link layer, while all other functionality is handled by the ROHC scheme itself.
A header compression scheme (such as a ROHC Profile) can be conceptualized and/or realized as a state machine. A challenging task is to keep the compressor and decompressor states, called contexts, consistent with each other, while keeping the header overhead as low as possible. There is one state machine for the compressor, and one state machine for the decompressor. The compressor state machine directly impacts the level of compression efficiency, as it is an important part of the logic controlling the choice of compressed packet type to be sent. The purpose of the decompressor state machine is mainly to provide the logic for feedback (if applicable) and to identify the packet types for which decompression may be attempted.
A compression context contains and maintains relevant information about past packets, and this information is used to compress and decompress subsequent packets. As explained in the ROHC documentation, the context of the compressor is the state it uses to compress a header. The context of the decompressor is the state it uses to decompress a header. Either of these or the two in combination are usually referred to as “context”, when it is clear which is intended. The context contains relevant information from previous headers in the packet stream, such as static fields and possible reference values for compression and decompression. Moreover, additional information describing the packet stream is also part of the context, for example information about how the IP Identifier field changes and the typical inter-packet increase in sequence numbers or timestamps.
A packet that provides the means for the decompressor to verify successful decompression is a context-updating packet. Because decompression can be verified, this type of packet can update the context. For ROHC, context-updating packet types carry a Cyclic Redundancy Code (CRC) within their format; this is a checksum calculated over the original uncompressed header. This CRC is used to verify successful decompression of each packet; when successful, the context can be updated.
A packet that relies on other means to guarantee successful decompression—i.e. a packet format does not provide the means for the decompressor to verify successful decompression, and that only carries the information necessary for the decompression itself, is a self-contained packet. These packets do not update the context.
The ROHC (profiles defined in RFC 3095, RFC 3242, RFC 3408, “IP-ONLY” (Jonsson, L. and G. Pelletier, RObust Header Compression (ROHC): A compression profile for IP, IETF RFC 3843, June 2004) and “ROHC-UDPLite” (Pelletier, G., RObust Header Compression (ROHC): Profiles for UDP-Lite, Internet Draft (work in progress), RFC 4019, April 2005) all support three different modes of operation. In short, for a specific context, the mode of operation controls the actions and the logic to perform as well as the packet types to use during different states of the header compression operation. Packet types and formats that are allowed may vary from one mode to the other. The Unidirectional mode (U-mode) is used at the beginning of any ROHC compression before any transition to other modes may occur. The Bidirectional Optimistic mode (O-mode) seeks to maximize the compression efficiency and sparse usage of the feedback channel. The Bidirectional Reliable mode (R-mode) seeks to maximize robustness against loss propagation and context damage propagation.
When in U-mode, packets are sent from compressor to decompressor only. The U-mode is thus usable over links where a return path from decompressor to compressor is either not desired or not available. Periodical refreshes are used in U-mode. The U-mode is particularly applicable to broadcast or multicast channels.
The O-mode is similar to the U-mode, with the difference that a feedback channel is used to send error recovery requests and (optionally) acknowledgements of significant context updates from the decompressor to compressor.
Note that for most ROHC profiles, the U-mode and the O-mode are often indistinctly referred to using the term U/O-mode. This is because the U-mode and the O-mode have rather similar characteristics, such as an identical set of packets formats for both modes as well as a similar logic to perform context updates. This logic is called the optimistic approach, and provides robustness against packet losses for the context update procedure in U/O-mode. See also [RFC 3095 [ROHC], section 5.3.1.1.1] for more details.
The R-mode differs significantly from the two other modes. In particular, the R-mode uses a few different packet types only understood and useful in this mode. However, the R-mode differs mainly by making a more extensive usage of the feedback channel and it uses a stricter logic for performing context updates. This logic is based on the secure reference principle, and provides robustness against packet losses for the context update procedure in R-mode. See also [RFC 3095 [ROHC], section 5.5.1.2] for more details.
The header compression profiles defined in RFC 3095 [ROHC] were designed with the assumption that the channel between the compressor and the decompressor will not reorder the header-compressed packets; the channel is required to maintain packet ordering for each compressed flow. This assumption was motivated because the channels initially considered as potential candidates to use ROHC did guarantee in-order delivery of packets. This assumption was useful to improve compression efficiency and the tolerance against packet loss, objectives that were ranked highest on the requirement list at the time. The profile for compression of IP headers only [IP-ONLY] and the profiles for UDP-Lite are essentially extensions to the profiles found in [RFC 3095 [ROHC]]. Therefore, these profiles also inherit the same assumption of in-order delivery.
A header compressor can use an “optimistic approach” to reduce header overhead when performing context updates. The compressor normally repeats the same update until it is fairly confident that the decompressor has successfully received the information. The number of consecutive packets needed to obtain this confidence is typically open to implementations, and this number is normally related to the packet loss characteristics of the link where header compression is used. All the packet types used with the optimistic approach are context updating.
A header compressor can use a “secure reference principle” to ensure that context synchronization between compressor and decompressor cannot be lost due to packet losses. Using the secure reference principle, the compressor obtains its confidence that the decompressor has successfully updated the context from a context-updating packet based on acknowledgements received by the decompressor. However, most packet types used with the secure reference principle are self-contained and thus not meant to update the context.
The IETF Audio-Video Transport (AVT) working group (WG) is working on header compression over multiple hops. While header compression is mainly intended to address low-speed links where bandwidth is scarce, saving bandwidth in backbone facilities is also of importance due to the high costs and considerable amount of traffic carried within. Header compression can be applied point-to-point between each node in the backbone network, however this requires that packets be decompressed and recompressed at each node. Processing can be lowered by performing compression between non-adjacent nodes in the backbone network, over a multi-hop path.
For example, a multi-hop path can be a Multi-Protocol Label Switched (MPLS) route in the backbone network, or an IP tunnel. A higher packet loss rate and possible reordering of packets characterize such virtual links, spanning over multiple hops. This can result from packets being re-routed, or simply discarded at a node, due to congestion or failure of a node. Requirements for header compression over multiple hops are described in Ash. J., Goode. B. and Hand, J., Requirements for Header Compression over MPLS, Internet Draft (work in progress), RFC 4247, November 2005 [“AVT-HC”], and Ash, J., et al., Protocol Extensions For Header Compression Over MPLS, IETF Internet Draft AVT Working Group, <draft-ietf-avt-hc-over-mpls-protocol-07.txt>, May 2006.
The IETF Robust Header Compression (ROHC) working group (WG) is working on robust header compression, and will likely soon target an update to its RFC 3095 main specification to adjust its compression profiles so that they can handle reordering while maintaining the excellent robustness characteristics of today's ROHC profiles.
An encoding method known as the Least Significant Bit (LSB) encoding method is used to encode header fields whose values are usually subject to small changes, such as sequence numbers (SN), e.g. the RTP protocol sequence number (SN) or the sequence number created at the decompressor when compressing protocols that do not have sequence numbering within their header format. The Least Significant Bit (LSB) encoding method, the k least significant bits of the field value are sent instead of the entire field value, where k is a positive integer. When receiving those bits, the decompressor derives the original value using a previously received value v_ref.
The Least Significant Bit (LSB) encoding method is guaranteed to give the it correct result if both the compressor and decompressor use “interpretation intervals” in which the original value resides and in which the original value is the only value that has the same LSB bits as those transmitted. The concept of an interpretation interval is illustrated in FIG. 1. As illustrated in the interpretation interval of FIG. 1, the parameter p (known as the “interval shift parameter” or “offset”) is used to shift the interpretation Its interval with respect to the previously received value v_ref.
Another encoding method which is a derivate of the Least Significant Bit (LSB) encoding method and which is known as Window-LSB encoding, uses a window of candidate v_ref. With the secure reference principle, acknowledgements from the decompressor allow the compressor to remove the values of v_ref that are older than the one acknowledged from the sliding window LSB and W-LSB are described in [RFC 3095 [ROHC]]. More specifically, the interpretation interval can be clearly divided in two (sub)intervals, e.g., subinterval “reordering” and subinterval “robustness”, as shown in FIG. 2.
In summary, correct interpretation of the encoded value using LSB coding depends on: (1) a sufficient number of encoded bits to recover the correct value within the correct interval; (2) a sufficiently large reordering subinterval to palliate or abate possible reordering; and (3) a sufficiently large robustness subinterval to palliate possible packet losses, or packets temporarily missing as they are being reordered.
One consequence of the secure reference principle (where not all packets are context updating) is that only the values acknowledged by the decompressor are included as references in the encoding sliding window (e.g. LSB or W-LSB coding). This robustness principle allows compressed packets to be sent with a format that does not include means for the decompressor to verify correct decompression (using. e.g., a checksum over the original uncompressed header), as the reception of LSB encoded bits applied to the secure reference is sufficient for correct decompression. The most optimal packet type in R-mode, packet type 0 (R-0), as well as packet type R-1*, do not carry any Cyclic Redundancy Code (CRC), that is a checksum calculated over the uncompressed header. These packet types account for most of the header-compressed traffic. Decompression entirely relies on the cumulative effect of previous updates to the secure reference, and the compressed data is based on the current value of the reference—which must be the same for both the compressor and the decompressor. This is suitable when in-order delivery between compressor and decompressor is guaranteed.
However, if reordering can occur, the consequence of this robustness principle is that the decompressor does not have the means to verify the decompression of self-contained packets, i.e., not meant to update the secure reference; these packets normally account for the majority of the packets exchanged between compressor and decompressor.
In order to minimize robustness issues when operating in R-mode. more sequence number (SN) bits may be sent and/or the interpretation interval can be modified to allow more values to be within the interpretation interval for reordering.
Now consider the 3GPP2 EV-DO (Evolution for Data Only) forward link, to provide a value for the worst-case reordering depth. For 3GPP2 EV-DO (Evolution for Data Only) forward link, the following expression provides the out-of-order delay, in ms:delay(out-of-order)=[#transmission slots]*[interleaver depth]*[slot time period]
Consider a configuration using a 16-slot transmission on ARQ-1, followed by 1-slot transmission on ARQ-2:
[# transmission slots]=16−2 (accounts for the end of ARQ-2 transmission)
[interleaver depth]=4
[slot time period]=1.667 ms
The worst-case delay in the forward link is 106.24−3.334=102.906 ms. If Delayed-ARQ is used, there will be an additional time delta to recognize that a packet sent over ARQ-1 was not received and the same packet gets sent out again. Assuming the delta is 10 ms, the out-of-order depth becomes 2*106.24+10=222.48 ms.
So in other words, for a 20 ms service such as VoIP, the maximum reordering depth in packets on the forward link can be up to 222.48/20, which is roughly 11 packets.
Current state-of-the-art in header compression use packet formats that are predefined with a fixed number of bits for each fields. Some packet formats, through the usage of extensions for which presence is explicitly conveyed within the packet formats themselves, may provide additional bits to some fields. This is particularly useful to increase the interpretation interval of the LSB encoding.
Specifically, for ROHC profiles defined in RFC 3095 [ROHC], the interval shift parameter p is defined as follows:
For profiles 0x0001, 0x0003 and 0x0007:                p=1, when bits (SN)<=4;        p=2^(bits(SN)-5)−1 otherwise.        
The interpretation interval for these conventional ROHC profiles is expressed by Table 1. As shown in Table 1, the ability for ROHC to handle packets that are out-of-order depends on the number of bits sent in each packet. For example, a sequentially late packet of type 0 (with either 4 or 6 bits of SN) sets the limit to one packet out of sequence for successful decompression to be possible.
TABLE 1Offset p(2{circumflex over ( )}k − 1) − pbits (SN) k(reordering)(losses)4114503161627312487248915496
On the other hand, for profiles 0x0002, 0x0004 and 0x0008, the “interval shift parameter” or “offset” parameter p=−1, independently of bits(SN). A value of p=−1 means that the interpretation interval offset can only take positive values, and that no sequentially late packet can be decompressed if reordering occurs over the link.
In summary, according to Table 1, in order to guarantee robustness for the 1xEV-DO link, at least 9 bits of the sequence number (SN) should be sent at any time. This would provide for a maximum reordering event of 300 ms, as well as abate 495 consecutive packet losses. Considering that this link is certainly reliable enough as to guarantee less than a few consecutive packet losses, and considering that having nine bits of sequence number forces the use of a packet type that is at least 2-3 octets larger than the smallest compressed packet size, the tradeoff is not well balanced.
The drawback of the above approach is that packet formats are tailored for only some specific scenarios. For example, with ROHC, packet formats are defined so that they can handle a maximum expected number of consecutive losses over the link, while handling a very small number of reordering (or in some cases, none at all).
There is thus a trade-off with this approach when designing robust packet formats that can handle both robustness to packet losses and a large enough reordering depth in a general manner, that will work for any type of link. When operating in the most efficient compression, many fields remain static and unchanged while others have established linear functions to a sequence number, such as the RTP sequence number (SN) field. Thus, simply carrying enough bits for that sequence number allows carrying changes for all header fields. The trade-offof using the LSB interpretation interval is illustrated in FIG. 3.
With the upcoming deployment of wireless links with higher bit rates and lower latencies (still relatively high latency with respect to the bit rate), the in-order delivery assumption is no longer applicable. Such links include 3GPP High-Speed Data Packet Access (HSDPA), 3GPP2 (Evolution for Data and Voice) EV-DV and 3GPP2 (Evolution for Data Only) EV-DO.
Thus, there is a need, as also described in Kapoor, R., Haipeng J. and M. Kretz, Robust Header Compression (ROHC): Support for Reordering and Constant IP-ID, Internet Draft (work in progress), <draft-ietf-kapoor-rohc-rtp-new-requirements-00.txt>, March 2005, for the different scenario of IP tunnels in the wired infrastructure, for header compression algorithms to be robust not only against packet losses, but also against reordering of packets. The problem thus lies in making the trade-off between the reordering and robustness intervals as efficient as possible, for any type of link characteristics/configuration, within the compression algorithm itself.
Work on header compression over multiple hops is ongoing in the IETF. The AVT WG is defining related requirements, see, e.g., Ash, J., Goode, B. and Hand. J., Requirements for Header Compression over MPLS, Internet Draft (work in progress), RFC 4247, November 2005, and Ash, J, et al., Protocol Extensions For Header Compression Over MPLS, IETF Internet Draft AVT Working Group, <draft-ietf-avt-hc-over-mpls-protocol-07.txt>, May 2006. It is expected that the working group will then complete work that will likely enable at least eCRTP (see, e.g., Koren, T., Casner, S., Geevarghese, J. Thompson B. and P. Ruddy, Enhanced Compressed RTP (CRTP) for Links with High Delay, Packet Loss and Reordering, IETF RFC 3545, IETF Network Working Group, July 2003) and ROHC (see, e.g., Carsten Bormann, et al. RObust Header Compression (ROHC): Framework and four profiles: RTP, UDP, ESP and uncompressed, IETF RFC 3095, April 2001) to be used over reordering links, as a result of these requirements.
As mentioned earlier, some header compression algorithms (e.g. ROHC) may have been designed with the assumption that the channel between compressor and decompressor delivers packets to the decompressor in the same order as when coming out of the compressor. This means that a state-of-the-art compressor will normally select the most optimal packet type based on the characteristics of the header to be compressed and based on the context, not based on the possible reordering characteristics of the link.
This also means that a state-of-the-art compression algorithm will not have the capability to handle both reordering and robustness in an efficient way for any type of reordering/loss pattern of a link layer.
FIG. 4 shows a typical example of the interpretation interval, e.g., state of the art with the LSB interpretation interval. The table of FIG. 4 shows values that clearly indicate a bias towards handling packet losses (robustness) with respect to handling reordering. A packet with 4 bits of SN would allow a reordering depth of 1 packet, but sustain up to 14 consecutive losses prior to its reception in order to be successfully decompressed.
For a link where the decompressor experiences that the loss pattern is almost non-existent (close to zero losses), but packets may be reordered to up to, e.g., 14 packets, it would require the compressor to use at least 9 bits of SN—much more than would be required in this case. In addition, the packet formats with the higher number of LSB bits normally are less efficient, normally carrying more than sequencing information.
Thus, summarizing in part the foregoing, the robustness and tolerance to reordering of the LSB encoding (e.g. in ROHC) are bound to the number of sequence number (SN) bits in the packet format, as well as the offset parameter p. In the prior art, the packet formats (PF) and the value of parameter p are defined statically for each profile. The RTP protocol sequence number (SN) in the most efficient compression operation is the only field for which bits are carried in compressed form, using, e.g., LSB coding (other fields can be decompressed based on the SN, or are not changing).
The interpretation interval defines how much reordering depth and how many consecutive packet losses the LSB coding will handle. Conventionally, both the offset parameter p and the number of sequence number (SN) bits in packets are fixed. However, the ratio of the intervals reordering/robustness is specific for different link technologies and configuration. For example, a high-speed link (1xEV-DO, HSDPA) can be reliable (˜0 losses) but have high reordering (up to 220 ms), or real-time (˜5-10% FER) with no reordering (0 retransmission).
What is needed, therefore, and an object of the present invention, are apparatus, techniques, and methods of header compression which are robust not only against packet losses, but also against reordering of packets.